Pattern matching generally refers to finding a pattern in a series of events that sufficiently resembles a given particular pattern, so that the series of events can be considered to comprise the given particular pattern. For pattern matching in computer image processing, series of events are images comprising pixels, which are the events. Patterns in the images are patterns of color values (including, optionally, black, white and grays) of pixels that typically define features, such as for example various objects, people and animals, in the images. Pattern matching with respect to a given image refers to determining whether a pattern of pixel color values in the given image sufficiently resembles that of an image of a particular feature so that it can be determined whether the given image comprises an image of the feature.
Generally, to perform pattern matching to locate a particular feature in a “target” image, a usually rectangular “mask-pattern” of pixel values that are considered to define an image of the feature is scanned across the target image. For each scan position, pixels in a region, hereinafter referred to as a “scan-window”, of the target image defined by a projection of the mask-pattern on the target image are compared to corresponding pixels in the mask-pattern to determine, responsive to a “similarity criterion”, whether corresponding pixels are similar. A distance, hereinafter a “separation distance”, between the mask-pattern and the scan-window is defined responsive to the pixel comparisons, and a decision is made responsive to the image separation distance as to whether the scan-window contains the feature. If the separation distance is considered small enough, the mask-pattern and the scan-window are considered to match and the scan-window and the image determined to comprise the feature. In some procedures a “brute force”, generally relatively slow procedure is used to determine whether a mask-pattern and a scan-window match, and each pixel in the scan mask-pattern is compared to each pixel in the image scan-window to provide a separation distance and therefrom as to whether there is a match.
D. I. Barnea and H. F. Silverman in an article entitled “A Class of Algorithms for Fast Digital Image Registration; IEEE Trans. Computer, vol. 21, no. 2. pp. 179-186, February 1972, describe a relatively fast matching procedure referred to as a “Sequential Similarity Detection Algorithm”—(SSDA). In accordance with the method, pixels in a mask-pattern are repeatedly, randomly chosen and compared to corresponding pixels in an image scan-window and the sum of absolute differences of the intensity values of compared pixels accumulated. If, as pixels are compared, the accumulated sum exceeds a predetermined threshold, the scan-window and the mask-pattern are determined to be dissimilar and not to match. After a predetermined number of comparisons, if the sum does not exceed the threshold, the mask-pattern and the image scan-window are determined to match. The method is considered to be relatively inaccurate and result in a relatively high incidence of mistaken decisions: decisions, referred to as “false positives”, in which a scanning mask-pattern and an image scan-window are determined to match when in fact they don't; and decisions, referred to as “false negatives”, in which a scanning mask-pattern and image scan-window are determined to mismatch when in fact they match.